#include <vector>
#include <iostream>

using namespace std;

struct ListNode
{
    int val;
    ListNode * next;
    ListNode() : val(0), next(nullptr)
    {}
    ListNode(int val) : val(val), next(nullptr)
    {}
    ListNode(int val, ListNode * next) : val(val), next(next)
    {}
};

class Solution 
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        if(headA == nullptr || headB == nullptr)
        {
            return nullptr;
        }
        ListNode * _dummyHeadA = new ListNode(0, headA);
        ListNode * _dummyHeadB = new ListNode(0, headB);
        ListNode * cur = _dummyHeadA;
        int lengthA = 0;
        int lengthB = 0;
        while(cur->next != nullptr)
        {
            cur = cur->next;
            lengthA++;
        }
        cur = _dummyHeadB;
        while (cur->next != nullptr)
        {
            cur = cur->next;
            lengthB++;
        }
        if(lengthA < lengthB)
        {
            swap(_dummyHeadA, _dummyHeadB);
            swap(lengthA, lengthB);
        }
        int gap = lengthA - lengthB;
        ListNode * curA = _dummyHeadA;
        ListNode * curB = _dummyHeadB;
        for(int i = 0; i < gap; i++)
        {
            curA = curA->next;
        }
        ListNode * result = nullptr;
        while(curA != nullptr)
        {
            if(curA == curB)
            {
                result = curA;
                break;
            }
            curA = curA->next;
            curB = curB->next;
        }
        delete _dummyHeadA;
        delete _dummyHeadB;
        return result;
    }
};

// 辅助函数：创建链表
ListNode* createList(vector<int>& vals) 
{
    if(vals.empty()) return nullptr;
    
    ListNode* head = new ListNode(vals[0]);
    ListNode* cur = head;
    for(int i = 1; i < vals.size(); i++) 
    {
        cur->next = new ListNode(vals[i]);
        cur = cur->next;
    }
    return head;
}

// 辅助函数：打印链表
void printList(ListNode* head) 
{
    cout << "[";
    while(head) 
    {
        cout << head->val;
        if(head->next) cout << ",";
        head = head->next;
    }
    cout << "]";
}

// 辅助函数：创建相交链表
pair<ListNode*, ListNode*> createIntersectingLists(vector<int>& listA, vector<int>& listB, vector<int>& intersect, int skipA, int skipB) 
{
    // 创建相交部分
    ListNode* intersectHead = nullptr;
    if(!intersect.empty()) 
    {
        intersectHead = createList(intersect);
    }
    
    // 创建链表A
    ListNode* headA = nullptr;
    if(!listA.empty()) 
    {
        headA = createList(listA);
        if(intersectHead) 
        {
            ListNode* cur = headA;
            for(int i = 0; i < skipA && cur; i++) 
            {
                cur = cur->next;
            }
            if(cur) cur->next = intersectHead;
        }
    } 
    else 
    {
        headA = intersectHead;
    }
    
    // 创建链表B
    ListNode* headB = nullptr;
    if(!listB.empty()) 
    {
        headB = createList(listB);
        if(intersectHead) 
        {
            ListNode* cur = headB;
            for(int i = 0; i < skipB && cur; i++) 
            {
                cur = cur->next;
            }
            if(cur) cur->next = intersectHead;
        }
    } 
    else 
    {
        headB = intersectHead;
    }
    
    return {headA, headB};
}

int main() 
{
    Solution solution;
    
    // 测试案例1: 相交链表
    cout << "测试案例1 (相交链表):" << endl;
    vector<int> listA1 = {4, 1};
    vector<int> listB1 = {5, 6, 1};
    vector<int> intersect1 = {8, 4, 5};
    auto [headA1, headB1] = createIntersectingLists(listA1, listB1, intersect1, 1, 2);
    cout << "链表A: ";
    printList(headA1);
    cout << endl;
    cout << "链表B: ";
    printList(headB1);
    cout << endl;
    ListNode* result1 = solution.getIntersectionNode(headA1, headB1);
    cout << "相交节点值: " << (result1 ? to_string(result1->val) : "null") << endl;
    cout << "期望: 8" << endl << endl;
    
    // 测试案例2: 相交链表（不同长度）
    cout << "测试案例2 (不同长度相交):" << endl;
    vector<int> listA2 = {1, 9, 1};
    vector<int> listB2 = {3};
    vector<int> intersect2 = {2, 4};
    auto [headA2, headB2] = createIntersectingLists(listA2, listB2, intersect2, 2, 0);
    cout << "链表A: ";
    printList(headA2);
    cout << endl;
    cout << "链表B: ";
    printList(headB2);
    cout << endl;
    ListNode* result2 = solution.getIntersectionNode(headA2, headB2);
    cout << "相交节点值: " << (result2 ? to_string(result2->val) : "null") << endl;
    cout << "期望: 2" << endl << endl;
    
    // 测试案例3: 不相交链表
    cout << "测试案例3 (不相交链表):" << endl;
    vector<int> listA3 = {2, 6, 4};
    vector<int> listB3 = {1, 5};
    vector<int> intersect3 = {};
    auto [headA3, headB3] = createIntersectingLists(listA3, listB3, intersect3, 0, 0);
    cout << "链表A: ";
    printList(headA3);
    cout << endl;
    cout << "链表B: ";
    printList(headB3);
    cout << endl;
    ListNode* result3 = solution.getIntersectionNode(headA3, headB3);
    cout << "相交节点值: " << (result3 ? to_string(result3->val) : "null") << endl;
    cout << "期望: null" << endl << endl;
    
    // 测试案例4: 一个链表为空
    cout << "测试案例4 (一个链表为空):" << endl;
    vector<int> listA4 = {1, 2, 3};
    ListNode* headA4 = createList(listA4);
    ListNode* headB4 = nullptr;
    cout << "链表A: ";
    printList(headA4);
    cout << endl;
    cout << "链表B: null" << endl;
    ListNode* result4 = solution.getIntersectionNode(headA4, headB4);
    cout << "相交节点值: " << (result4 ? to_string(result4->val) : "null") << endl;
    cout << "期望: null" << endl << endl;
    
    // 测试案例5: 两个链表都为空
    cout << "测试案例5 (两个链表都为空):" << endl;
    ListNode* headA5 = nullptr;
    ListNode* headB5 = nullptr;
    cout << "链表A: null" << endl;
    cout << "链表B: null" << endl;
    ListNode* result5 = solution.getIntersectionNode(headA5, headB5);
    cout << "相交节点值: " << (result5 ? to_string(result5->val) : "null") << endl;
    cout << "期望: null" << endl << endl;
    
    // 测试案例6: 单节点相交
    cout << "测试案例6 (单节点相交):" << endl;
    ListNode* common = new ListNode(1);
    ListNode* headA6 = common;
    ListNode* headB6 = common;
    cout << "链表A: ";
    printList(headA6);
    cout << endl;
    cout << "链表B: ";
    printList(headB6);
    cout << endl;
    ListNode* result6 = solution.getIntersectionNode(headA6, headB6);
    cout << "相交节点值: " << (result6 ? to_string(result6->val) : "null") << endl;
    cout << "期望: 1" << endl << endl;
    
    // 测试案例7: 相同长度相交
    cout << "测试案例7 (相同长度相交):" << endl;
    vector<int> listA7 = {1, 2};
    vector<int> listB7 = {3, 4};
    vector<int> intersect7 = {5, 6};
    auto [headA7, headB7] = createIntersectingLists(listA7, listB7, intersect7, 1, 1);
    cout << "链表A: ";
    printList(headA7);
    cout << endl;
    cout << "链表B: ";
    printList(headB7);
    cout << endl;
    ListNode* result7 = solution.getIntersectionNode(headA7, headB7);
    cout << "相交节点值: " << (result7 ? to_string(result7->val) : "null") << endl;
    cout << "期望: 5" << endl << endl;
    
    // 测试案例8: 从头开始相交
    cout << "测试案例8 (从头开始相交):" << endl;
    vector<int> common8 = {1, 2, 3};
    ListNode* commonHead = createList(common8);
    ListNode* headA8 = commonHead;
    ListNode* headB8 = commonHead;
    cout << "链表A: ";
    printList(headA8);
    cout << endl;
    cout << "链表B: ";
    printList(headB8);
    cout << endl;
    ListNode* result8 = solution.getIntersectionNode(headA8, headB8);
    cout << "相交节点值: " << (result8 ? to_string(result8->val) : "null") << endl;
    cout << "期望: 1" << endl << endl;
    
    return 0;
}